package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Set;

public class LC12 {
    private  boolean ans = false;
    public boolean wordBreak(String s, Set<String> dict) {
        traceback(new ArrayList<>(),s,0, (ArrayList<String>) dict);
        return ans;
    }
    public void traceback(ArrayList<String> temp, String s, int start, ArrayList<String> dict){
        if(start>dict.size()) return;
        StringBuffer ss = new StringBuffer();
        for (int i = 0; i < temp.size(); i++) {
            ss.append(temp.get(i));
        }
        if(ss.equals(s)) ans = true;
        for (int i = 0; i < dict.size(); i++) {
            if(!temp.contains(dict.get(i))){
                traceback(temp,s,start+1,dict);
            }
        }
    }
}